package C059.graph;

/**
 * ClassName: ChainForwardStar
 * Package: C059.graph
 * Description: 链式前向星
 *
 * @Author BCXJ
 * @Create 2025/9/25 07:53
 * @Version 1.0
 * @Since 1.0
 */
public class ChainForwardStar implements GraphInterface{

    // 头结点
    int[] head;
    // next数组
    int[] next;
    // to数组
    int[] tos;
    // 权重数组
    int[] weights;

    int n , m ;
    int cnt; // 边的编号, 默认为0

    // 边初始化，点数组初始化，边数组初始化
    @Override
    public void init(int n, int m) {
        this.n = n;
        this.m = m;
        head = new int[n + 1];
        next = new int[m + 1];
        tos = new int[m + 1];
        weights = new int[m + 1];
        cnt = 1;
    }

    @Override
    public void init(int n) {

    }


    @Override
    public void addEdge(int from, int to, int weight) {
        next[cnt] = head[from];
        head[from] = cnt;
        tos[cnt] = to;
        weights[cnt ++] = weight;
    }


    /**
     *     1(邻居、边权) : (5,5) (4,1)
     *     2(邻居、边权) : (4,6) (3,7) (5,4)
     *     3(邻居、边权) : (2,7) (4,2) (5,4)
     *     4(邻居、边权) : (2,6) (3,2) (1,1)
     *     5(邻居、边权) : (1,5) (2,4) (3,4)
     */
    @Override
    public void print() {
        System.out.println("=================前式链向星===============");
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻边、边权)：");
            int cur = head[i];// 当前边
            while(cur != 0) {
                System.out.print(String.format("(%s, %s)", tos[cur], weights[cur]));
                cur = next[cur];
            }
            System.out.println();
        }
    }
}
